package com.LeeCode;

/**
 * 寻找旋转排序数组中的最小值 II
 */

public class Code154 {
    public static void main(String[] args) {
        int[] nums = {3, 1, 3, 3};
        System.out.println(new Code154().findMin(nums));
    }

    public int findMin(int[] nums) {
        int left = -1, right = nums.length - 1;
        int n = nums.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[n])
                left = mid;
            else if (nums[mid] < nums[n]) {
                right = mid;
                n = right;
            } else { // 无法确定mid位于那个区间，但是right一定位于递增区间
                right--;
                n = right;
            }
        }
        return nums[right];
    }
}
